Miller-Rabin randomized primality test (1976, 1980)

There is a randomized algorithm running in $O(n^3 \log_2(1/\delta))$ time that, with probability $1-\delta$ determines if an $n$ -bit integer $x$ is prime.

MillerRabin(n)
If $n > 2$ and $n$ is even, return composite.
/* Factor $n − 1$ as $2^s t$ where $t$ is odd. */
$s ← 0$
$t ← n − 1$
while $t$ is even
$s ← s + 1$
$t ← t/2$
end /* Done. $n − 1 = 2^s t$ . */
Choose $x ∈ \{1, 2, . . . , n − 1\}$ uniformly at random.
Compute each of the numbers $x_t , x^{2t} , x^{4t} , . . . , x^{2^st} = x^{n−1} \mod n$ .
If $x^{n−1} \not\equiv 1 \pmod n$ , return composite.
for $i = 1, 2, . . . , s$
If $x^{2^i t} ≡ 1 \pmod n$ and $x^{2^{i−1} t} \not\equiv ±1 \pmod n$ , return composite.
end /* Done checking for fake square roots. */
Return probably prime.